939 428
536055713 289600145 70868290 682688378 780162192 743437205 439549284 703894760 458011422 675413407 723533749 54074691 154111503 437132075 382320530 359814706 563265274 236692393 276800108 245606287 725133515 444227583 617049163 373614569 495158339 328681732 146552902 137071363 8778355 480249862 508446476 86652499 737247557 850344773 89363294 595592580 116072947 532334198 937676946 692343028 589889934 259230528 237807378 413645879 282020728 205333954 629027035 52719762 712682 610163467 525130239 395117440 542210671 472357281 746034979 329428785 559435879 328706043 560897537 447414534 793171845 782443271 185323495 203568662 725267538 517709477 118156855 32415149 145427624 460632617 858602213 879134151 953795127 390947549 398924540 631808409 854593795 365194876 403132185 836399113 207065059 793674169 713356782 674507825 173372676 931312310 54942401 460086752 979572837 790064013 241370602 137597976 845109337 477378763 25942872 696682385 520025608 949539312 572944653 335661365 93100525 699243504 498276254 703324322 218568281 383976373 224928948 556781739 738337775 995081370 432715661 656803799 46936614 197302001 844769147 944085217 223322058 685067391 484938852 147895606 659983740 570036475 250153792 130134394 12569645 631195282 818814623 307843075 225912743 829024870 21015328 174905180 102525700 149348618 619744763 481815236 905198389 785784584 879990648 270091437 42215292 744571227 694663542 231283517 189248498 54068213 890464229 671244496 532098562 998556218 840883020 37818996 707251436 423974275 10261828 397045867 387805251 904347037 511442170 111556269 480557679 693174599 220799409 15008611 553263404 118594231 867088190 317354861 763343369 110031382 352158346 456326877 357569258 938587135 406559764 664699770 467247751 81344516 254157932 143636798 124622571 891650345 373836985 52291288 846565365 930106983 209725236 179744299 882151386 491065130 770925995 502751437 434772385 701034964 18587647 629530249 455119781 474865720 715956902 904996830 255417879 996844575 947342634 130862717 456314746 193405383 40284839 403301838 435583781 178411102 236109393 905003372 110530501 368383115 354540524 172822948 717655512 445096678 36004434 674710523 312441906 263408251 596668913 31794085 131399804 27996492 403142986 97120782 421038000 712964812 196654451 729043285 542631071 425818212 387677846 379011788 417271915 201721329 422980208 801131898 399208717 153253444 572360403 641745049 738272208 149361569 627303460 744644120 741966292 399129153 65996765 12634393 400946828 486553296 755337484 912279156 136065088 577661679 451239635 546634035 776794764 902288819 855216870 435338004 949492447 681357348 244634128 449510154 322851581 354683327 342087854 919019964 566413694 794921717 17657650 980000773 116583500 607529386 481459873 579503474 878363945 731442102 300999446 87811783 480342567 661853543 112775741 366143611 909998126 701863421 757076440 857936183 728823673 113865261 150783550 633206874 114655769 375262367 983152343 158032504 370325105 940036208 679453345 15673814 742091704 546100657 261618862 62186736 908226170 704548837 946444452 109062388 325504279 910030983 716560187 89561668 866057283 897453954 720659651 561107192 537188228 632628663 225060251 6608218 723689911 699149691 237426363 962239592 585586060 701903126 734912555 855034965 454918149 470694213 512909193 741676296 991761659 159378360 586082952 38563483 195178393 261313941 728636779 161981405 147378911 732940787 386312078 69794513 444636704 566342240 61932510 146198317 820934020 201577820 62040411 775299292 135051911 685427931 65934237 584199804 364405880 756389575 276191564 240842209 65060091 667751292 184987815 857744 148936840 120037963 195241470 979412549 378470121 435446263 710407736 199273837 755143616 657114938 567531854 420202413 770704127 451905857 497816782 408846937 201411437 383086636 405285977 468711677 749665576 680699792 330448421 465827288 142204958 249519348 802637691 92749916 90536082 17743959 518096698 94585264 613829022 68230312 343925330 851096878 238305707 771268685 457316426 460787429 368745722 815707549 241065404 224694295 481482270 741620582 83602131 710375356 632571520 217655655 316226515 378807550 199161562 898798807 476856210 769825723 500211133 20880605 260841463 594731271 142864907 282331413 400863362 247497639 857704317 45796369 153116868 362847382 883607326 367270870 962415842 849238404 13371853 640393307 54674454 131588434 408816320 401297421 770397998 358667927 608781308 404780110 732016395 130398750 474669277 113983985 507214628 777307494 454130325 383517120 64364544 109728544 283616933 999206135 101220287 716530613 934151525 278797254 257374866 623755198 697658498 185786322 378508095 258068618 944924026 550573748 35299742 806082715 722829346 794857080 876246302 297958953 657882401 577638944 294469441 712187293 689712754 291057183 54421531 135063575 525156326 7313631 594635479 459651562 134177695 112897339 798522930 877966618 763785879 704240901 84638974 299588581 231295255 255721857 511784609 900809015 28800320 189722600 650518419 502341940 618816901 368607207 927516643 26691506 217469743 835093533 431784371 376138428 549645528 190760608 51959223 592113936 534088944 799368569 756691387 597634210 430221884 435011363 736347418 619995927 282766417 832446224 265926983 819049547 150055965 548068388 479653448 437360331 898136159 783473464 91159861 196012636 701642794 994744216 234572990 87854194 232504166 906416518 48280483 384097978 539674959 874251957 11648313 882101136 713014004 456260814 755459052 642773641 305320889 910158830 60119991 445716715 140577750 39673638 788609709 220560432 637472981 716731642 774732148 754092167 963189783 403078627 774460869 851686227 422855504 812286157 264357614 190810026 366341383 88218009 194551376 366938839 413879063 182859676 41079264 529749720 749199665 714704926 846428842 967590112 90676056 261202141 579431241 675282902 932900451 574207111 665811569 579059925 110519934 175619395 882004838 415836074 926309289 347597609 39759490 429771609 309315640 89712837 335055795 382565017 909262161 919274904 912968954 320956499 688742257 949097111 234958061 73416230 476166887 153596074 652162357 257754342 164559960 514885934 410733329 93649689 716511033 659458676 590748114 332764025 4349016 379698752 537747293 120272244 678345300 627008074 371745964 633932719 855566880 986064576 23943757 4790911 139863428 362716354 439025889 118264942 351824284 910584037 276447134 851966652 843157847 236176305 572809934 999068636 105762809 328016419 164782670 184353778 360263065 706145836 510610448 204380508 272605092 969867055 301494937 280083750 135698776 979518087 282050947 663664020 2241610 523542527 987695612 928358556 706918625 441070168 459917638 646910057 259779800 355227078 885750581 811235801 466120128 945148019 67354292 272972032 484287867 707136763 754143296 314472867 506203842 713375983 415582827 503769022 986268577 781636434 141567579 256803839 336184822 749679391 867246664 536599624 774134773 43096000 929420801 297352753 146537126 57203608 241457000 340847491 173626981 826652283 880341233 967317694 266943842 330421809 574228519 238383508 269094943 884858103 766523944 880421228 645170165 157236733 157986340 628546016 365158287 479016936 975405025 748925247 46503276 61467986 470783034 480731404 602841185 237893957 48688539 373122172 649989141 370553796 572106887 581884668 915139460 588897347 497903635 976803498 65116029 974904874 478010472 736793815 852891940 135051093 770331460 413075083 507552368 766681750 841775225 911490305 871192750 62138418 680220269 95656486 177170684 545148000 119865497 860828446 620154063 539003342 214660618 11946688 939097198 572879387 169799139 933185045 767878516 115823710 437866457 140298460 966292306 36667294 789300405 874143753 571963850 343665495 715121366 667215938 674597749 397058043 926103724 12075105 79605822 207672687 84070718 723777013 994988517 516377482 402524325 773118912 936400510 587545753 150655631 890532922 970796271 639292382 610904253 26590732 733620085 292473868 938198917 123909271 858435103 370055117 822473296 410782827 809911122 574143548 786415645 527204816 583210051 145260907 510268413 462881088 607401856 731266271 260934549 717741034 504836456 427686927 376316319 94339121 346918062 591756008 536485481 554034219 541658842 878951500 721987156 746418723 662520519 488392846 497875030 115516696 357181222 917050871 494110841 464470844 306864378 588531525 274964570 961745525 878436891 554379815 76030378 486256863 875498419 806839234 92134577 221343559 960120515 711947567 448406726 672375218 837573791 198660090 104147672 734937044 571845486 701157028 443386856 811272090 951241387 299212067 918406028 248283041 775310247 919383901 851629678 718961084 93897732 57054640 463196875 530037617 172122683 808687469 509222645 132172925 300516375 324463960 106160081 651985740 784792888 740318762 850104666 535599489 465084818 345552143 320439580 282082932 270944747 245878313 611455673 443216815 51548256 79744267 925382248 896123761 788207840 414444862 912827249 582256427 227371951 439585983 389040306 714972677 290842085 427297919 891780381 212992858 477532141 81044194 230503992 373207351 419437574 339116609 506400923 127813856 142441669 103052648 125924982 229776716 621374865 330336792 622687752 374721444 833685286 516242310 566731305 936927688 750134803 587482330 826621121
281600713 853508924 940924337 372014414 200597360 725409880 550152860 487197026 11679926 223630964 256304543 855655715 419052618 338806382 129206962 636145610 588382478 529772922 610051140 738671652 195619738 293558177 94596531 864638740 711878840 151326269 328819156 242819087 858502630 807413375 422398322 844881310 814752215 411546089 676686279 757469152 309863666 17126100 481317636 688322821 517560786 537994476 349172431 362767316 75605444 956650414 571937472 961742374 926304076 399159025 462397155 818346344 416479392 905151834 271734329 770537757 67875371 207961830 824124726 499710298 881709324 435235684 363975236 148419401 825322900 379242744 618039871 646647718 446898124 208792218 600166136 773243717 893791724 856068245 74377138 437424522 320932069 858389256 528182696 3814639 300963545 646620264 708714117 759851906 589526429 981411324 745445610 666297700 390061374 337870944 22894315 125546827 706049657 667454467 308827794 672090368 525432129 606195625 88715355 667151330 480525116 905243881 924258743 442395490 158451783 746314415 737516937 586768773 682001646 596869564 865590955 805519205 70562037 390583073 382808170 842359216 884103634 113498824 954007302 178840359 13586223 732865515 651310644 283077409 113662317 541506971 367665052 436363269 265534492 989436218 489199450 923541459 980440708 564079873 330557569 609706652 176553504 192999035 393486739 964256005 544467742 679774984 217080586 447751881 288889056 819061851 254222803 7437620 502858877 169512188 557843918 157534632 704489280 657428167 590633039 545164828 208442152 253777772 435632800 943663000 630917479 791277 813327997 805462202 576635108 437196834 623885974 634201140 86838969 542722872 369782032 900954443 409110197 114719278 111744004 163944538 888432602 439374679 772219391 553719629 598097632 642319322 589193345 339831334 161057969 66383925 947506302 143919996 431607531 414996662 80217824 203542263 107045473 257926145 593019650 959949781 710185882 835292045 803332918 797479272 47643984 532911654 734956865 660394390 41329395 536742508 20779738 289437016 290743076 214267219 480694318 869842235 193273402 311322786 398689887 956026850 19261120 814012788 52854272 265025153 30396917 595197625 421620635 469179748 272460874 211992502 630001707 649706598 777547240 630712961 44234146 259047803 879714600 898190470 814396260 711050022 973734680 224340741 226567882 241594115 256918525 271401873 901288353 934179391 999305163 524904082 231045800 464806938 578278063 957172164 223045653 47089772 922386822 248885430 745274385 658441758 667210851 994057036 49616695 214422956 716537101 455682622 290288921 463891882 382423934 328965015 345731259 864141116 990388837 806352694 998763286 308890268 886326693 840030544 954328983 422584727 731070164 641648876 11347101 283652624 920411069 534762085 559336446 411681404 450736862 680604140 67668354 779462757 961647595 506789380 274175847 760169704 430530633 425688580 267173596 398797622 179671444 592415385 295603846 816981270 738469401 887505985 54811901 932019042 242031964 825803728 701853520 863448709 238270612 878625007 435354493 164026628 642639658 65779864 608113402 411875826 158397758 544975260 183033135 572246393 930296354 726145309 865264121 734311768 910154972 843289876 262059049 83389792 448558760 950850764 311555587 912346614 933496180 735721829 854154688 606569621 945477219 361478738 67418636 615280201 862596683 952058843 740736136 987169332 110325815 993147804 40100425 427164172 592177125 545918724 530156631 808603803 409154120 513150423 922222127 651052094 601130503 415924397 933254210 298278247 963852797 288728432 691548276 544131356 685682103 208653794 884899997 234932597 706394617 67179541 815344907 455929889 753600313 170872561 902809854 453834466 619302946 342055089 931281707 487902220 877496339 274453862 228525114 204621066 941451678 336192882 140471624 211090649 471738633 769302543 861033574 219813515 995986640 750660550 367041304 673582534 319196193 264135928 862511318 803918147 132620638 611649113 75594126 411935055 275566239 617587055 915876384 365465677 625480237 439170839 832591585 434953521 913827080 565638657 370267673 564829190 238408546 306978095 959331973 161848426 476179234 200922234 885456853 957819917 502253155 397496589 472991023 199691574 170338290 777648616 501860266 337140541 984621523 107189342 552591060 521586962 347486652 206595223 208613677 798425525 810528152 35278351 584420010 28118204 332400133 60985365 186458418 555472592 720441046 162524749 550436644 308053551 155620755 748133167 817483728 696820012 279102964 200168581 884711417 764371115 780716138 323633137 165762650 746480294 175721622 369920869 124528669 29151914 406728144 909366696 330337637 985650778 742017441 405933784 362201542 521866731 257475657 83031779 393287879 428069543 559433018 383078924 544940135 459949930 452877210 686467436 197403029 308195624 57821893 1284975 538095287 884231525 270291658 965844051 96804900 914629819 126663913 320748204 92860074 338351960 7822363 109194723 581529609 831037821 119592842 327369906 675927925 528509440 689180436 935928233 444843544 372071115 147022284 561580973 522997133 945833306 213423225 159018612 166234727 955704641 782471190 97404170 937855144 100433060 720971344 536094798 991452234 773739198 80387595 286289781 731895738 196041818 236868574 444955271 860384343 280110173 754180242 397694173 940281592 429124154 19518886 34305961 322485347 355026044 458952142 323015790 235387863 510551872 109143920 67649412 68390787 538316984 840245029 436849814 591336204 284306345 354720318 542720803 191204875 879367661 142039357 958145280 152330893 792420083 599266391 581944532 872727953 165522490 414639097 343023770 365075341 816116185 625824576 530463779 528810218 909405946 183201407 28629905 372901507 950671962 154412989 348657629 897948714 750985931 294221620 837108051 156399908 613360563 376926164 219747857 912030887 511723915 313846717 489855627 622152803 212559968 444662473 10448906 249432310 122473556 162808063 379353896 689304694 179531294 881189665 202496085 237384940 432543622 108436767 924858966 618636499 369704426 195676322 109243072 731987357 842033341 804577666 467065985 696874030 532228610 28870736 561884760 395739487 579848917 708973261 796326744 268993660 286842338 95423601 550234985 455340487 488437228 263422181 727181767 1678579 509902920 617755273 936874369 230358441 223236447 813457647 964149243 821424134 58529584 147625822 287012716 81344283 572998603 910160208 284061025 824410988 407481815 897511668 611419448 243967858 680060684 403510189 234698918 246156825 159090874 740394640 911391794 212192578 604539969 525183722 559409591 190248514 533829527 467372216 731054310 24093794 967579077 498852654 306710978 563635549 299887978 96818481 992543010 594818020 33263414 515534812 231696178 88618013 584091248 527143679 849050098 934430752 808217457 798568347 139991989 885705337 246077991 569396839 722477988 452740265 555004563 421293646 326442553 213674917 472590155 870524143 195639236 581722197 845475833 643305756 951813866 139673110 704059866 573114203 303565088 668741433 808389695 72522344 482844468 9842562 545824015 273925553 466605509 550796969 707104579 77267417 965748166 284210396 449821545 630834485 256170239 813581627 783076899 639011410 826721420 198649435 592271013 760776301 608820572 548735172 340060473 889479673 826462387 928845171 152554942 318544669 572263080 606438489 279237669 646637619 170159272 868823769 266052851 542740043 571981809 783432270 427448259 683432358 989002264 865286275 793503681 857120315 412221316 318409273 990756911 236337717 899709424 182985125 737322724 759593074 746647277 100218606 551191239 929011974 889134173 488336563 430265433 688912310 254723321 53953668 347099689 484590718 6005453 23901028 822519645 597419019 792094135 533633614 292350511 781595202 956506091 270850221 772966510 582125751 209899633 52220642 995465721 641422647 320455589 762303169 986128200 580882495 802786231 476550164 498401763 851184514 254606633 666380055 863644392 522694246 237814612 662964986 416143753 664635015 186813667 766942819 830104460 51900467 878221909 100266473 392025545 886940909 104247935 663954074 562983600 646440427 214151432 504409717 658396352 898120344 981593836 733087985 523829009 749470994 925330682 406392181 855005643 620866733 778557014 355957725 536768173 711966318 854531831 882351868 444259719 264547216 754195498 804474132 393620160 934750723 157711117 914160223 892910032 865535720 429762837 444074890 93370311 604792086 653238920 455985205 187397573 662384536 123543812 270562676 338563456 477471789 729507830 196172369 851526081 907159495 565340964 16531527 490829542 966753036 465173284 165853640 760696674 842650328 608370658 483887801 11518009 242079929 635863326 68533489 529386885 592892786 470024428 940430013 125094131 46439289 355890226 395583839 849304134 856382328 432156973 284308362 399804371 226991311 75227628 478789096 448485636 952709136 549579987 928807316 814557910 160893314 872205594 283663008 821322842 864609696 858737996 725307537 123754807 816169879 91799497 744246494 235595302 400417227 644551492 218264948 707830645 882425426 8136517 294603061 933551493 239761271 503013543 768477300 438062924 345757241 30525979 233183098 540828372 635560137 583330468 826425605 264321978 846612240 967718425 800950980 646942640 404995366 924668327 296619996
